Exercise: Hash Tables - Data Structures with Generic Types in Python

Task#

Implement an addSlow() method for adding an element x to a LinearHashTable, which simply stores x in the first null array entry it finds.

Sample input

100 random elements

Expected output

The expected output will be as follows:

Adding
Searching
The value 96 is not found
The value 88 is not found
The value 62 is found
The value 23 is not found
The value 2 is found
The value 22 is not found
The value 89 is found
The value 61 is not found
The value 50 is not found
The value 4 is not found

main.py

base.py

utils.py

from utils import new_array
from base import BaseSet
import random
# Number of bits
w = 32
# Main class
class LinearHashTable(BaseSet):
    
    def __init__(self, iterable=[]):
        self._initialize()
        self.initialize()
        self.add_all(iterable)
        
    def _initialize(self):
        self.dl = object()
    # Initialize function    
    def initialize(self):
        self.d = 1
        self.t = new_array((1<<self.d))
        self.q = 0
        self.n = 0
    # Function to resize the table
    def _resize(self):
        self.d = 1
        while ((1<<self.d) < 3*self.n): self.d += 1
        told = self.t
        self.t = new_array((1<<self.d))
        self.q = self.n
        for x in told:
            if x is not None and x != self.dl:
                i = self._hash(x)

Enter to Rename, Shift+Enter to Preview

Task to implement addSlow() in LinearHashTable